#include <stdio.h>
#include "hashtable-openHash.h"
#include <stdlib.h> //malloc  memset->string.h
#include <string.h>

//NULL =(void*)0 是否=0？是否需要强制转化？
/**
 * 思路：
 *     [A B C D E F ...] 每一个结点的其中一个元素都是链表的头结点，同时也有记录该链表的长度的
 *      1 4 6 N N N				通过哈希函数找到该元素在哈希表中的位置，如果没有发生冲突，它就是头结点
 *      2 5 7					否则头结点的下一个结点就是它。尾节点指向NULL
 *      3 N N
 * 		N
 * 	    搞清楚哈希表element的类型或者组成元素，剩下的就是逻辑了
 * 
 * 
 * */

/**
 * 初始化哈希表，
 * */
void HtInit(HTELEM **ht,int cap)
{
	if(cap > HASH_TABLE_CAPACITY) return;
	int i =0;
	for(i=0;i<cap;i++)
	{
		ht[i] = (HTELEM*)malloc(sizeof(HTELEM)); //申请空间 sizeof(HTELEM) = 12
		//这里应进行malloc申请判断是否成功，下面的函数就不俑判断了
		if(ht[i] == NULL) return;
		memset(ht[i],0,sizeof(HTELEM));
	}

}

/** BKDR hash function 对string进行散列得到一个整数值，得到整数值之后再进行哈希函数的运算*/
unsigned int BkdrHash(HtElemType* keyString)
{
	unsigned int seed = 131;
	unsigned int hash = 0;
	while(*keyString != '\0' && *keyString != '\n')
	{
		hash = hash * seed + *keyString; 
		*keyString ++;
	}
	return (hash & 0x7FFFFFFF); //取低31位
}

/**
 * 取余的哈希函数
 * */
unsigned int HashFunc(unsigned int hashKey,int htLen)
{
	return (hashKey%htLen );
}

/**
 * 求htelem index
 * */
unsigned int HtIndex(HtElemType* keyString,int htLen)
{
	unsigned int hashKey = BkdrHash(keyString);
	return (HashFunc(hashKey,htLen));
}

/**
 * 得到哈希表所有的元素的个数,2种办法
 * */
unsigned int HtElemNum(HTELEM** ht,int htLen)
{
	int i = 0;
	unsigned int len = 0;
	for(i=0;i<htLen;i++)
	{
		len = len + ht[i]->listLen;
	}

	return len;
}

//第2种方法
unsigned int HtElemNum2(HTELEM** ht,int htLen)
{
	int i = 0;
	for(i = 0;i<htLen;i++)
	{
		HTELEM* t = ht[i];
		while(t->next != NULL)
		{
			htLen++;
			t = t->next;
		}
	}

	return htLen;
}

/**
 * 打印哈希表所有元素
 * */
static void PrintHt(HTELEM** ht,int htLen)
{
	
	HTELEM* t = NULL;
	int i = 0;
	for(i=0;i<htLen;i++)
	{
		t = ht[i];
		printf("The length of the linked list where this object resides %d\n",t->listLen);
		while(t != NULL)
		{

			printf("%s \n", t->keyString);
			t = t->next;
		}
	}

}


/**
 * 哈希表的插入，根据hashKey寻找下标，用链表解决冲突
 * 1-succ 0-fail
 * */
static int InsertElemToHt(HTELEM** ht,HtElemType* keyString,int htLen)
{
	//本来是要进行地址是否有效的判断的
	int index = HtIndex(ht,htLen);
	if(ht[index] == NULL) //如果头结点为空，还没有数据，这赋值给头结点
	{
		ht[index]->keyString = keyString;
		ht[index]->listLen++;
		ht[index]->next = NULL;
	}
	else
	{
		HTELEM* t = ht[index];
		while(t->next != NULL) t = t->next;
		t->next = (HTELEM*)malloc(sizeof(HTELEM));
		t->next->keyString = keyString;
		ht[index]->listLen++;
		t->next->next = NULL;
		return 1;
	}
	return 0;
}

/**
 * 哈希表删除某个元素，as the same time the elem must be free
 * 1-success 0-fail
 * */
int DelElemInHt(HTELEM** ht,HtElemType* keyString,int htLen)
{
	if(keyString == NULL) return 0;
	int index = HtIndex(keyString,htLen);
	HTELEM* t = ht[index];
	HTELEM* tPre = t;

	int len = ht[index]->listLen;
	while(t != NULL) //逐个查找
	{
		if(strcmp(t->keyString,keyString) == 0)
		{
			if(t == ht[index])
			{

				ht[index] = t->next;
				ht[index]->listLen = (--len);
				FREE(t);
				return 1;

			}
			//不是头结点
			else
			{
				ht[index]->listLen--;
				tPre->next = t->next; //跳过t结点
				FREE(t);
				return 1;
			}
		}
		tPre = t;
		t = t->next;

	}

	return 0;
}

/**
 * 哈希表结点值的获取
 * 返回该节点地址
 * */

HTELEM* GetElemInHt(HTELEM** ht,HtElemType* keyString)
{
	
}